In complex systems such as telecommunications or computer networks, system performance is influenced by a huge number of variables. Optimizing system performance frequently depends on detecting the presence of a particular set of variables, and gaining an understanding of its behavior. The determination of whether, for example, a particular trend or pattern of importance is present in the variables, can be accomplished by measuring the system variables, and then presenting the results conventionally in terms of numerical data values in print media or on a monitor. These materials usually are voluminous, however, and a visual inspection of the data does not readily reveal the presence of any trend of interest. To the vast majority of human viewers, the numerical portrayals are abstractions from which it is difficult or impossible to derive or discover needed useful information on critical characteristics.
To make possible a quick comprehension of the inner structure of data sets, and particularly to detect characteristics, trends and patterns within a many-variable system, visual analogs of the dataset are finding increasing use. For example, as described in the Bell Labs News, p. 2, Dec. 18, 1997, pictorial representations can be created which show details of interest regarding telecommunications network operation that otherwise are buried in large databases. The pictorial display greatly facilitates a viewer's ability to discern the presence of critical characteristics or patterns in the data. By way of illustration, in the real-time operation of a telecommunications network it is critical to know the changing dynamics of traffic buildup along routing paths; and to take action to reroute traffic to avoid blocking. A pictorial display allows even a lay viewer to make the determination.
The pictorial formats must be calculated as efficiently as possible, however, in order to allow real time operation or simply to conserve computer time. Efficient calculation methodology is therefore a prerequisite.
In 3-dimensional modeling, a selected three of the n-subsets present in a dataset are combined into a 2-dimensional presentation which has the visual attribute of appearing as a 3-D figure. Certain datasets are especially amenable to a 3-dimensional modeling technique known as volume rendering. The process is a low-albedo approximation to how volume data generates, scatters, or occludes light energy. Specifically, effects of the light interaction at each data set location are integrated continuously along the viewing rays according to the following equation: ##EQU1##
where .chi. is the origin of the ray, .omega. is the unit direction vector of the ray, .differential.(s) is the differential attenuation at .chi.+s.omega., and I(t) is the differential intensity scattered at .chi.+t.omega. in the direction -.omega.. Volume rendering in accordance with Eq. (1) can be performed with object-order, image order or domain techniques. In the volume approach, 3-D models of the surface are represented by 3-D volume rasters. A regular volume raster consists of the intersection points of three grids, each point being a sample point or "voxel" in 3-D space. The underlying continuous model of the subject can be reconstructed from the discrete voxel values according to the sampling theorem.
The most widely-used image-order rendering method is called volume ray casting as described, for example, in the article by M. Levoy, Display of Surfaces from Volume Data, IEEE Computer Graphics & Applications 8, 5 (May 1988). The volume ray casting computation typically is divided into three steps: (1) traversing and uniform sampling along the ray; (2) shading the sampling points according to an illumination model to get the color of the sampling points; and (3) compositing the sampling points to derive the final color of the voxel.
One of the main problems in volume ray casting is that use of uniform sampling wastes much time in transversing empty or homogeneous regions. Several optimization techniques to avoid time-intensive calculations appear in the literature. One is the pyramid structure described by M. Levoy, Efficient Ray Tracing of Volume Data, ACM Transactions on Graphics 6, 1 (July 1990). A second is the empty space skipping approach described by R. Yagel and Z. Shi in Accelerating Volume Animation by Space-leaping, IEEE Visualization '93 Proceedings, October, 1993. A third is importance sampling described by J. Dauskin and P. Hanrahan in Fast Algorithms for Volume Ray Tracing, 1992 ACM Workshop on Volume Visualization, October 1992. The optimization of the required calculations involved in several approaches by using wavelet transforms has also been attempted.